The present invention relates to the field of computer systems, and more specifically to a method and system for multiplying large numbers on a computer system.
Many computer applications require the multiplication of large numbers. For example, some situations when such a need arises are when computers are used for processing or simulating scientific data, or executing a cryptographic system.
Cryptography systems may be used for scrambling private messages, for applying a crack-proof signature on an e-mail message, or for providing for secure online transactions. At their core, modern cryptography systems require two very large numbers, typically 1024 bit or larger, to be multiplied together. However, most modern computer microprocessors only have the native capability to multiply 32 or 64 bit numbers. Thus, software techniques are needed to multiply numbers greater than the processor""s native capabilities.
Such software techniques govern the amount of time required by the microprocessor to multiply these large numbers. Thus, inadequate software techniques can negatively affect the system""s performance. Moreover, as the use of e-commerce and other secure online transactions increase, there is a need for faster software multiplication techniques so that users can complete transactions quickly.
For the reasons stated above, and for other reasons stated below which will become apparent to those skilled in the art upon reading and understanding the present specification, there is a need in the art for a faster method for the multiplication of large numbers on a computer system.
In one embodiment, a computer-implemented method for multiplying two large multiplicands includes generating a plurality of partial products by multiplying each digit of the first multiplicand with each digit of the second multiplicand and adding each of the most significant digits of each partial product to an appropriate location in a first array and adding each of the least significant digits of each partial product to an appropriate location in a second array. The method includes adding the first array to the second array, wherein the result is the product of the two original multiplicands. This and various other embodiments are described and claimed below.